1. Field of the Invention
The present invention relates to a method for decoding error correcting codes, a program storing the method for decoding error correcting codes, and a device for the method for decoding error correcting codes and more particularly to the method for decoding error correcting codes that can be used suitably for digital mobile communications systems such as a portable cellular phone or a like and the program of the decoding method and the device for the decoding method.
The present application claims priority of Japanese Patent Application No. 2002-239492 filed on Aug. 20, 2002, which is hereby incorporated by reference.
2. Description of the Related Art
Recently, as an error correcting code, Turbo codes that can realize, by performing realistic processing, a transmission characteristic being near to a limit of information theory (being called a “Shannon's limit”) have been developed. The Turbo codes are described below.
FIG. 17 is a schematic diagram of a conventional encoder to produce Turbo codes being one of PCCCs (Parallel Concatenated Convolutional Codes). As shown in FIG. 17, the encoder of the example is so configured that two pieces of convolutional encoders 1 and 2 are concatenated in parallel through an interleaving device 3. The convolutional encoder 1 encodes a first parity bits “p” using an information sequence (systematic bits “u”) to be fed from an outside. The interleaving device 3 produces interleaved systematic bits “u′” obtained by sorting each bit of the systematic bits “u”. This processing is called as “interleaving”. This interleaving device 3 feeds it to the convolutional encoder 2. The convolutional encoder 2 encodes a second parity bits “p′” using the interleaved systematic bits “u′”. A set of the systematic bits “u” and the first parity bits “p” is called a first element code (u, p) and a set of the interleaved systematic bits “u′” and the second parity bits “p′” is called a second element code (u′, p′).
On the other hand, a method for decoding the Turbo codes is featured in that the decoding is iterated while a priori probability being reliable information is exchanged between the first element code (u, p) decoding and the second element code (u′, p′) decoding. The method for decoding the Turbo codes employs a soft-input and soft-output decoding method. The soft-input and soft-output decoding method can be roughly classified into two methods, one being a SOVA (Soft-Output Viterbi Algorithm) decoding method and another being a MAP (Maximum A-Posteriori) decoding method. A Max-Log-MAP algorithm being one type of the MAP decoding method is described below. In the Max-Log-MAP algorithm, the Viterbi decoding is performed on a trellis diagram to calculate a Path Metric.
FIG. 18 is a trellis diagram. FIG. 19 is a diagram of a procedure of ordinary decoding. Processing in which the Viterbi decoding is performed from a start point to an end point on the trellis diagram to calculate a path metric value is called “forward processing” and the path metric value calculated with the forward processing is called an “α” path metric value (αPMor first path metric value). The α path metric value is stored in a memory as shown in FIG. 19. On the other hand, processing in which the Viterbi decoding is performed in a direction being reverse to the direction employed in the forward processing to calculate a path metric value is called “backward processing” and the path metric value is called a “β” path metric value (β PMor second path metric value). Moreover, processing in which Log-Likelihood Ratio (LLR) (Logarithm ratio of a posteriori probability) is calculated from the α path metric value, the β path metric value and a branch metric value and then extrinsic information is calculated is called “extrinsic information value calculating”. Here, the extrinsic information value represents an increment of reliability for information sequence. The extrinsic information value is actually used as a priori probability to be exchanged between the first element code (u, p) decoding and the second element code (u′, p′) decoding.
Next, the Max-Log-MAP algorithm is explained in detail. First, an output of the convolutional encoder occurring at time k, since it is a systematic code, is set to be (uk, pk)ε{±1} (pk being a parity bits) and a corresponding input of the convolutional decoder yk is set to be (yku, ykp). Estimated information sequence uhk is set to be (uh1, uh2, . . . uhN). FIG. 20 is a diagram of a transition model in a case when a transition from a time point (k−1) to a time point k on the trellis diagram takes place. When a specified state on the trellis diagram at the time k is defined to be a state SK and a specified state on the trellis diagram at time (k−1) is defined to be a state sK−1, Log-Likelihood Ratio L (uhk) in the Max-Log-MAP algorithm is given by equation (1).
                              L          ⁡                      (                          u              hk                        )                          =                                                                              max                  ⁢                                                                                                          (                                                            s                                              k                        -                        1                                                              ,                                          s                      k                                                        )                                                                              u                  k                                =                                  +                  1                                                      ⁢                          {                              I                ⁢                                                                  ⁢                n                ⁢                                                                  ⁢                                  p                  ⁡                                      (                                                                  s                                                  k                          -                          1                                                                    ,                                              s                        k                                            ,                      y                                        )                                                              }                                -                                                                      max                  ⁢                                                                                                          (                                                            s                                              k                        -                        1                                                              ,                                          s                      k                                                        )                                                                              u                  k                                =                                  -                  1                                                      ⁢                          {                              In                ⁢                                                                  ⁢                                  p                  ⁡                                      (                                                                  s                                                  k                          -                          1                                                                    ,                                              s                        k                                            ,                      y                                        )                                                              }                                                          Equation        ⁢                                  ⁢                  (          1          )                    
In equation (1), “p (sK−1, sK, y)” denotes concurrent occurrence probability for an input “y” of the convolutional decoder and a transition from the state sK−1 to the state sK. That is, the pre-defined information L (uhK) of a k-th information bit uK is defined as a difference between a maximum probability out of the concurrent occurrence probability p(sK−1, sK, y) for all the transitions (sK−1→sK) that take place due to uK=+1 and a maximum probability out of the concurrent occurrence probability p(sK−1, sK, y) for all the transitions (sK−1→sK) that take place due to uK=−1. When an input of the convolutional decoder to be supplied during time “i” to time “j” is expressed by equation (2) and when a codeword length is N, the concurrent occurrence probability p sK−1, sK, y) in a memoryless channel is given as a sum of independent probability expressed by equation (3).Yij=(yi, yi+1, . . . , yj)  Equation (2)p(sk−1,sk,y)=p(sk−1,Y1k−1)+p(sk,yk|sk−1)+p(YkN|sk)  Equation (3)
In equation (3), each term of a right side is expressed in order from the left respectively as αK−1(sK−1), γk(sK, sK−1) and βk(sK). Out of them, γk(sK, sK−1) is a branch metric value for all the existing transitions (sK−1→sK). αK−1(sK−1) is a path metric value calculated by the forward processing and βk(sK) is a path metric value calculated by the backward processing, each of which can be recursively calculated by equations (4) and (5).
                                          α            k                    ⁡                      (                          s              k                        )                          =                              max                          s                              k                -                1                                              ⁢                                          ⁢                      {                                                            γ                  k                                ⁡                                  (                                                            s                                              k                        -                        1                                                              ,                                          s                      k                                                        )                                            +                                                α                                      k                    -                    1                                                  ⁡                                  (                                      s                                          k                      -                      1                                                        )                                                      }                                              Equation        ⁢                                  ⁢                  (          4          )                                                              β                          k              -              1                                ⁡                      (                          s                              k                -                1                                      )                          =                              max                          s              k                                ⁢                                          ⁢                      {                                                            γ                  k                                ⁡                                  (                                                            s                                              k                        -                        1                                                              ,                                          s                      k                                                        )                                            +                                                β                  k                                ⁡                                  (                                      s                    k                                    )                                                      }                                              Equation  (5)            
FIG. 21 is a diagram of a model of calculating αK−1(sK−1), γk(sK, sK−1) and βk(sK) in a case where a transition from the time (k−1) to the time k on the trellis diagram takes place. However, the start and end points on the trellis diagram are unique and are initialized as shown in equation (6).
                                          α            0                    ⁡                      (                          s              0                        )                          =                  {                                                                                                                1                      ,                                                                                                                                                    if                          ⁢                                                                                                          ⁢                                                      s                            0                                                                          =                        0                                            ,                                                                                                                                  0                      ,                                                                                                                          if                        ⁢                                                                                                  ⁢                                                  s                          0                                                                    ≠                      0.                                                                                  ⁢                                                          ⁢                                                β                  N                                ⁡                                  (                                      s                    N                                    )                                                      =                          {                                                                                          1                      ,                                                                                                                                                    if                          ⁢                                                                                                          ⁢                                                      s                            N                                                                          =                        0                                            ,                                                                                                                                  0                      ,                                                                                                                          if                        ⁢                                                                                                  ⁢                                                  s                          N                                                                    ≠                      0.                                                                                                                              Equation        ⁢                                  ⁢                  (          6          )                    
Moreover, an extrinsic information value can be calculated by using equation (7) and equation (8) from the pre-defined information L (uhK).Li(uk)=La(uk)+Lc×yku  Equation (7)Le(uhk)=L(uhk)−Li(uk)  Equation (8)“Li(uK)” expressed in equation (7) is called “internal information” against the extrinsic information Le (uhK). La(uK) expressed in equation (8) is a priori probability and also corresponds to an extrinsic information value in a process of decoding other element codes. “Lc” is a constant determined by a channel and is given by equation (9) in the case of a white Gaussian channel (the mean: 0, distribution N0/2, and signal power Eb).Lc=4Eb/N0  Equation (9)
The constant “Lc” is a value that depends on a noise condition of the channel.
The ordinary method for decoding Turbo codes described above has a problem in that path metric values at all points on the trellis diagram and in all states have to be held at once and therefore large capacity of a memory is required in order to hold the path metric values. To solve this problem, a method is proposed in which capacity of the memory required to hold the path metric values is reduced by performing local decoding using specified time intervals(called “windows”) on the trellis diagram. In this case, in an ordinary decoding sequence in which decoding is started from a start point on the trellis diagram, how to handle an initial value of a path metric value in the local backward processing presents a problem. A decoding method is disclosed in an article “Soft-Output Decoding Algorithm for Continuous Decoding of Parallel Concatenated Convolutional Codes” (S. Benedetto et al., Proceeding of IEEE International Conference on Communications, pp. 112-117, 1996) in which backward processing is performed with all trellis states existing ahead of the windows considered to be equally probable and a period during which an initial value of a path metric value is obtained by performing the backward processing is defined as a learning period This decoding method is called a “sliding window method”. Moreover, a decoder providing one method that can produce a soft-output in each cycle in the sliding window method is disclosed in an article “VLSI Architectures for Turbo Codes” (IEEE Transactions on VLSI system, pp. 369-379, 1999) in which backward processing modules corresponding in number to a number of time intervals for windows are provided and used in a pipeline arrangement. However, the disclosed decoder has a disadvantage in that it needs a number of backward processing modules corresponding to the number of windows, which increases circuit scale.
FIG. 22 is a schematic block diagram of a conventional decoder of Turbo codes, based on an article “An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes” (A. J. Viterbi, IEEE Journal on Selected Areas on Communications, pp. 260-264, 1998). The disclosed decoder has a learning module to perform learning processing in the sliding window method in which a decoding schedule is carried out by time-shifting by a number of time intervals corresponding to the size of the window provided, thus enabling production of a soft-output in every cycle. The disclosed decoder is made up of a forward processing module 11, a backward processing module 12, a learning processing module 13, an extrinsic information value calculating module 14, a switch 15, and memories 16, 17, 18, 19.
The forward processing module 11 performs forward processing. The backward processing module 12 performs backward processing. The learning processing module 13 performs learning processing. The extrinsic information value calculating module 14 calculates an extrinsic information value. The switch 15 is ordinarily connected to the backward processing module 12. When a learning result by the learning processing module 13 is fed to the backward processing module 12 as an initial value of a path metric value, the switch 15 is connected to the learning processing module 13. The memory 16 is placed to feed code elements and extrinsic information values to each of the forward processing module 11, backward processing module 12, and learning processing module 13. Also, the memory 17 is placed to feed path metric values calculated by the forward processing module 11 to the extrinsic information value calculating module 14. The memory 18 is placed to feed an extrinsic information value calculated by the extrinsic information value calculating module 14 to the memory 16. That is, the memory 18 is placed to exchange an extrinsic information value to be used as a priori probability information exchanged between the first element code (u, p) decoding and the second element code (u′, p′) decoding. The memory 19 is placed to temporarily store an interleaving pattern (ILP) therein. Moreover, the memories 16, 19 are structured as a bank of four memories and the memories 17, 18 are structured as a bank of two memories.
Next, operations of the decoder of Turbo codes having configurations shown above are described by referring to FIG. 23. In FIG. 23, “FWP” denotes forward processing, “BWP” denotes backward processing, and “STP” denotes learning processing.
(1) During time 0 to 2Lt, in order to perform learning processing described later, pre-processing to store element codes and extrinsic information existing from the time point 0 (start point) to 2LP on the trellis diagram as shown in FIG. 23 is performed. Moreover, to decode the second element code (u′, p′) decoding, processing to temporarily store the interleaving pattern (ILP) in the memory 19, in addition to the above pre-processing, is required.(2) During time 2Lt to 3Lt, the forward processing module 11 performs forward processing from the time point 0 (start point) to Lp on the trellis diagram as shown in FIG. 23. At the same time, the learning processing module 13 performs learning processing from the time point 2LP to LP on the trellis diagram as shown in FIG. 23. Moreover, an initial value of a path metric in the learning processing puts all states existing ahead of windows into an equal probability condition.(3) During time 3Lt to 4Lt, the forward processing module 11 performs forward processing from the time point LP to 2LP on the trellis diagram as shown in FIG. 23. Also, at the same time, the backward processing module 12 performs backward processing from the time point LP to 0 (start point) on the trellis diagram as shown in FIG. 23 subsequent to learning processing in (2) in FIG. 23. At the same time, the extrinsic information value calculating module 14 calculates an extrinsic information value. Furthermore, at the same time, the learning processing module 13 performs learning processing from the time point 3LP to 2LP on the trellis diagram as shown in FIG. 23.(4) During time 4Lt to 5Lt, the forward processing module 11 performs forward processing from the time point 2LP to 3LP on the trellis diagram as shown in FIG. 23. Also, at the same time, the backward processing module 12 performs backward processing from the time point 2LP to LP on the trellis diagram as shown in FIG. 23 subsequent to learning processing in (3) as shown in FIG. 23. Also, at the same time, the extrinsic information value calculating module 14 calculates an extrinsic information value. Furthermore, the learning processing module 13 performs learning processing from the time point 4LP to 3LP on the trellis diagram as shown in FIG. 23.(5) During time 5Lt to (Nt−Mt+3Lt) (Mt≦Lt), same processing as the processing (3) and (4) is performed.(6) During time (Nt−Mt+3Lt) to (Nt+3Lt), the backward processing module 12 performs backward processing from the time point (NP-MP) to NP(end point) on the trellis diagram as shown in FIG. 23. At the same time, the extrinsic information value calculating module 14 calculates an extrinsic information value.(7) Processing (1) to (6) described above is performed as decoding processing to be performed on the first element codes (u, p) decoding and subsequently the decoding processing on the second element codes (u′, p′) decoding is performed in the same manner as for the above processing (1) to (6) and a series of the processing described above is handled as a first operation of iterative decoding.(8) After iterative decoding has been completed an appropriate numbers of times (about 10 times), by using sign bits of a Log Likelihood Ratio (LLR) in decoding processing on the second element codes (u′, p′) decoding, a hard decision on each of the estimated information sequence uhk is produced.
As described above, the conventional decoder of Turbo codes requires the learning processing module 13. Moreover, both the memory 16 to feed element codes and extrinsic information values to each of the forward processing module 11, backward processing module 12, and learning processing module 13 and the memory 19 to temporarily store an interleaving pattern (ILP) have to be as a bank of four memories structured. Also, in the learning processing being pre-processing to start decoding, a time period to temporarily store element codes and extrinsic information values corresponding to 2LP time intervals is required. There is a fear that the disadvantages described above occur not only in decoders to decode Turbo codes but also decoders to generally perform iterative decoding codes using convolutional codes by using the soft-input and soft-output decoding method of the MAP decoding type.